package DoExercise.HSP_ZCY.A009_图结构.A001_并查集;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.Stack;

/**
 * 最小生成树有2个特点：1 不会形成环 2 能连接所有的顶点 的树
 * <p>
 * 克鲁斯卡尔算法：将图中的所有边都去掉，将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环，将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环
 * <p>
 * 两者区别
 * 克鲁斯卡尔算法直接从最小的边开始选择，生成最小树，直接来，普里姆是从某个节点开始，每次选择当前节点所能选到的最小边，生成最小树，间接来。
 * <p>
 * 方法：
 * 1 对所有边的权重从小到大排序
 * 2 找到权重最小的边，判断其点是否在一个并查集里面（是否联通）
 * 3 如果在，跳过
 * 4 如果不在，将该点和一直点加入到一个联通集合中
 * 5 循环1-4，直到处理完所有的边
 * <p>
 * 如果是无向图，则需要根据已知的图返回另一半
 */
public class Code04_克鲁斯卡尔算法_K算法
{
    
    public static class MySets
    {
        public HashMap<Node, List<Node>> setMap;
        
        public MySets(List<Node> nodes)
        {
            for (Node cur : nodes)
            {
                List<Node> set = new ArrayList<Node>();
                set.add(cur);
                setMap.put(cur, set);
            }
        }
        
        public boolean isSameSet(Node from, Node to)
        {
            List<Node> fromSet = setMap.get(from);
            List<Node> toSet = setMap.get(to);
            return fromSet == toSet;
        }
        
        public void union(Node from, Node to)
        {
            List<Node> fromSet = setMap.get(from);
            List<Node> toSet = setMap.get(to);
            for (Node toNode : toSet)
            {
                fromSet.add(toNode);
                setMap.put(toNode, fromSet);
            }
        }
    }
    
    
    // Union-Find Set
    public static class UnionFind
    {
        // key 某一个节点， value key节点往上的节点
        private HashMap<Node, Node> fatherMap;
        // key 某一个集合的代表节点, value key所在集合的节点个数
        private HashMap<Node, Integer> sizeMap;
        
        public UnionFind()
        {
            fatherMap = new HashMap<Node, Node>();
            sizeMap = new HashMap<Node, Integer>();
        }
        
        public void makeSets(Collection<Node> nodes)
        {
            fatherMap.clear();
            sizeMap.clear();
            for (Node node : nodes)
            {
                fatherMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }
        
        private Node findFather(Node n)
        {
            Stack<Node> path = new Stack<>();
            while (n != fatherMap.get(n))
            {
                path.add(n);
                n = fatherMap.get(n);
            }
            while (!path.isEmpty())
            {
                fatherMap.put(path.pop(), n);
            }
            return n;
        }
        
        public boolean isSameSet(Node a, Node b)
        {
            return findFather(a) == findFather(b);
        }
        
        public void union(Node a, Node b)
        {
            if (a == null || b == null)
            {
                return;
            }
            Node aDai = findFather(a);
            Node bDai = findFather(b);
            if (aDai != bDai)
            {
                int aSetSize = sizeMap.get(aDai);
                int bSetSize = sizeMap.get(bDai);
                if (aSetSize <= bSetSize)
                {
                    fatherMap.put(aDai, bDai);
                    sizeMap.put(bDai, aSetSize + bSetSize);
                    sizeMap.remove(aDai);
                } else
                {
                    fatherMap.put(bDai, aDai);
                    sizeMap.put(aDai, aSetSize + bSetSize);
                    sizeMap.remove(bDai);
                }
            }
        }
    }
    
    /**
     * 权值排序，权重小堆顶
     */
    public static class EdgeComparator implements Comparator<Edge>
    {
        @Override
        public int compare(Edge o1, Edge o2)
        {
            return o1.weight - o2.weight;
        }
    }
    
    public static Set<Edge> kruskalMST(Graph graph)
    {
        UnionFind unionFind = new UnionFind();
        unionFind.makeSets(graph.nodes.values());
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
        for (Edge edge : graph.edges)
        {
            priorityQueue.add(edge);//权重小的堆顶
        }
        Set<Edge> result = new HashSet<>();
        while (!priorityQueue.isEmpty())//O(logM)
        {
            Edge edge = priorityQueue.poll();
            if (!unionFind.isSameSet(edge.from, edge.to))//如果不是一个集合，就联合，O(1)，否则就跳过
            {
                result.add(edge);
                unionFind.union(edge.from, edge.to);
            }
        }
        return result;
    }
}
